Proth prime

 ( Classes Of Prime Numbers ) 

$a^\{\backslash frac\{p-1\}\{2\}\}\backslash equiv\; -1\; \backslash pmod\{p\}.$

This theorem can be used as a probabilistic test of primality, by checking for many random choices of $a$ whether $a^\{\backslash frac\{p-1\}\{2\}\}\backslash equiv\; -1\; \backslash pmod\{p\}.$ If this fails to hold for several random $a$, then it is very likely that the number $p$ is composite number. This test is a Las Vegas algorithm: it never returns a false positive but can return a false negative; in other words, it never reports a composite number as "Probable prime" but can report a prime number as "possibly composite".

In 2008, Sze created a deterministic algorithm that runs in at most $\backslash tilde\{O\}((k\backslash log\; k+\backslash log\; N)(\backslash log\; N)^2)$ time, where Õ is the Soft O notation. For typical searches for Proth primes, usually $k$ is either fixed (e.g. 321 Prime Search or Sierpinski Problem) or of order $O(\backslash log\; N)$ (e.g. Cullen number search). In these cases algorithm runs in at most $\backslash tilde\{O\}((\backslash log\; N)^3)$, or $O((\backslash log\; N)^\{3+\backslash epsilon\})$ time for all $\backslash epsilon>0$. There is also an algorithm that runs in $\backslash tilde\{O\}((\backslash log\; N)^\{24/7\})$ time.

Fermat numbers are a special case of Proth numbers, wherein . In such a scenario Pépin's test proves that only base need to be checked to deterministically verify or falsify the primality of a Fermat number.

The project Seventeen or Bust, searching for Proth primes with a certain $t$ to prove that 78557 is the smallest Sierpinski number (Sierpinski problem), has found 11 large Proth primes by 2007. Similar resolutions to the prime Sierpiński problem and extended Sierpiński problem have yielded several more numbers.

Since divisors of $F\_n\; =\; 2^\{2^n\}\; +\; 1$ are always of the form $k\; \backslash times\; 2^\{n+2\}\; +\; 1$, it is customary to determine if a new Proth prime divides a Fermat number.

As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes. Its main projects include:

• general Proth prime search
• 321 Prime Search (searching for primes of the form $3\backslash times2^n+1$, also called Thabit primes of the second kind)
• 27121 Prime Search (searching for primes of the form $27\backslash times2^n+1$ and $121\backslash times2^n+1$)
• Cullen prime search (searching for primes of the form $n\backslash times2^n+1$)
• Sierpinski problem (and their prime and extended generalizations) – searching for primes of the form $k\; \backslash times\; 2^n+1$ where k is in this list:

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

As of June 2023, the largest Proth primes discovered are:

3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343 ().

The largest Proth primes of the second kind can be primality testing use the Lucas–Lehmer–Riesel test.

As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes of the second kind. Its main projects include:

• general Proth prime of the second kind search
• 321 Prime Search (searching for primes of the form $3\backslash times2^n-1$, also called )
• 27121 Prime Search (searching for primes of the form $27\backslash times2^n-1$ and $121\backslash times2^n-1$)
• Woodall prime search (searching for primes of the form $n\backslash times2^n-1$)
• Riesel problem (and their prime and extended generalizations) – searching for primes of the form $k\; \backslash times\; 2^n-1$ where k is in this list:

k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743 }

Also, Proth primes can optimize den Boer reduction between the Diffie–Hellman problem and the Discrete logarithm problem. The prime number 55 × 2²⁸⁶ + 1 has been used in this way.

As Proth primes have simple binary number representations, they have also been used in fast modular reduction without the need for pre-computation, for example by Microsoft.